package leetCodeTop100;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * 最长连续序列
 * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
 *
 * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
 *
 * 思路：首先将nums数组排序，然后遍历数组，用一个变量记录当前连续序列的长度，如果当前数字与前一个数字不相等，则将当前连续序列长度加1，否则将当前连续序列长度重置为1。
 * 思路2：使用set集合，将数组转换为set集合，然后遍历set集合，用一个变量记录当前连续序列的长度，如果当前数字与前一个数字不相等，则将当前连续序列长度加1，否则将当前连续序列长度重置为1。
 */
public class L_128 {
    // 使用思路2
    public int longestConsecutive(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        if(nums.length == 1){
            return 1;
        }
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        if(set.size() <= 1){
            return set.size();
        }
        List<Integer> list = set.stream().sorted().collect(Collectors.toList());
        int max = 1;
        int tmp = 1;
        int pre = list.get(0);
        for (int i = 1; i < list.size() ; i++) {
            if(list.get(i) - pre == 1){
                tmp++;
            }else {
                tmp = 1;
            }
            max = Math.max(max, tmp);
            pre = list.get(i);
        }
        return max;
    }

    public static void main(String[] args) {
        L_128 l_128 = new L_128();
        System.out.println(l_128.longestConsecutive(new int[]{0,3,7,2,5,8,4,6,0,1}));
    }
}
